#include "DynamicArray1.h"
#include <iostream>
#include <cmath>

DynamicArray::DynamicArray() : capacity(10), size(0)
{
    this->a = new ElementType[capacity];
    FreePtr = nullptr;
    ShowPtr = nullptr;
    Compare = nullptr;
}

// DynamicArray::DynamicArray(const DynamicArray &array)
// {
//     capacity = array.capacity;
//     size = array.size;
//     a = new ElementType[capacity];
//     for (int i = 0; i < size; i++)
//     {
//         a[i] = array.a[i];
//     }
// }

void DynamicArray::operator=(const DynamicArray &array)
{
    delete[] this->a;
    capacity = array.capacity;
    size = array.size;
    a = new ElementType[capacity];
    for (int i = 0; i < size; i++)
    {
        a[i] = array.a[i];
    }
}

DynamicArray::~DynamicArray()
{
    if(FreePtr)
        FreePtr(a);
    delete []a;
}


void DynamicArray::SetFreePtr(void (*FreePtr)(ElementType))
{
    this->FreePtr = FreePtr;
}

void DynamicArray::SetShowPtr(void (*ShowPtr)(ElementType))
{
    this->ShowPtr = ShowPtr;
}

void DynamicArray::SetCompare(bool (*Compare)(ElementType, ElementType))
{
    this->Compare = Compare;
}



// 尾插法
void DynamicArray::InsertTail(const ElementType &element)
{
    if (size >= capacity)
    {
        capacity *= 2;
        ElementType *newP = new ElementType[capacity];
        for (int i = 0; i < size; i++)
        {
            newP[i] = a[i];
        }
        delete[] a;
        a = newP;
    }
    a[size++] = element;
}

void DynamicArray::show()
{
    if (ShowPtr)
    {
        for (int i = 0; i < size; i++)
        {
            ShowPtr(a[i]);
        }
        std::cout<<std::endl;
    }
}

void DynamicArray::InsertSort(int start, int end)
{
    for (int i = start + 1; i <= end; i++)
    {
        int j = i;       // 当前要插入的数的下标
        ElementType temp = a[i]; // 要插入的值
        for (; j > start; j--)
        {
            if (Compare(a[j - 1],temp)) // 前面这个数比我大
                a[j] = a[j - 1];
            else // 前面这个数比我小
                break;
        }
        a[j] = temp;
    }
}

int DynamicArray::Partition(int start, int end)
{
    int left = start;
    int right = end;
    ElementType temp = a[left]; // 将最左边的值定为基准值
    while (left < right)
    {
        // 右边往左动，找比基准值小的数
        while (Compare(a[right],temp) && left < right)
            right--;
        if (left < right)
            a[left++] = a[right]; // 把右边比基准值小的数扔到左边

        // 左边往右动，找比基准值大的数
        while (Compare(temp,a[left]) && left < right)
            left++;
        if (left < right)
            a[right--] = a[left]; // 把左边比基准值大的数扔到右边
    }
    a[left] = temp;
    return left;
}

// 快速排序
void DynamicArray::FastSort(int start, int end, int depth, int MaxDepth)
{
    if (start >= end)
        return;
    // 递归深度超过了最大深度
    if (depth > MaxDepth)
    {
        // 改用插入排序
        InsertSort(start, end);
    }
    // 如果没有超过最大深度
    // 用快速排序
    else
    {
        int pos = Partition(start, end);
        FastSort(start, pos - 1, depth + 1, MaxDepth);
        FastSort(pos + 1, end, depth + 1, MaxDepth);
    }
}

void DynamicArray::Sort()
{
    FastSort(0, size - 1, 0, 2 * log2(size));
}


void DynamicArray::RemoveByIndex(int index)
{
    if (index < 0 || index >= size)
    {
        std::cout << "插入位置非法!\n";
        return;
    }
    for (int i = index; i < size - 1; i++)
    {
        a[i] = a[i + 1];
    }
    size--;
}


void DynamicArray::RemoveByElement(ElementType element)
{
    for (int i = 0; i < size; i++)
    {
        if (Compare(a[i],element))
        {
            RemoveByIndex(i);
            i--;
        }
    }
}

void DynamicArray::Duplicate()
{
    for (int i = 1; i < size; i++) // O(n)
    {
        if (Compare(a[i],a[i - 1]))
        {
            RemoveByIndex(i);
            i--;
        }
    }
}

// 头插法
void DynamicArray::InsertHead(const ElementType &element)
{
    if (size >= capacity)
    {
        capacity *= 2;
        ElementType *newP = new ElementType[capacity];
        for (int i = 0; i < size; i++)
        {
            newP[i] = a[i];
        }
        delete[] a;
        a = newP;
    }
    for (int i = size; i > 0; i--)
        a[i] = a[i - 1];
    a[0] = element;
    size++;
}

// 中间插入
void DynamicArray::InsertByIndex(const ElementType &element, int index)
{
    if (index < 0 || index > size)
    {
        std::cout << "非法插入位置!\n";
        return;
    }
    if (size >= capacity)
    {
        capacity *= 2;
        ElementType *newP = new ElementType[capacity];
        for (int i = 0; i < size; i++)
        {
            newP[i] = a[i];
        }
        delete[] a;
        a = newP;
    }
    for (int i = size; i > index; i--)
        a[i] = a[i - 1];
    a[index] = element;
    size++;
}

// DynamicArray DynamicArray::FindByElement(const ElementType &element)
// {
//     DynamicArray result;
//     for (int i = 0; i < size; i++)
//     {
//         if (Compare(a[i],element))
//             result.InsertTail(i);
//     }
//     return result;
// }


DynamicArray::ElementType DynamicArray::FindByIndex(int index)
{
    if (index < 0 || index >= size)
    {
        std::cout << "插入位置非法!\n";
        return nullptr;
    }
    return a[index];
}


int DynamicArray::BinarySearch(ElementType element)
{
    int left = 0;
    int right = size - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (Compare(a[mid],element))
            right = mid - 1;
        else if (Compare(element,a[mid]))
            left = mid + 1;
        else
            return mid;
    }
    return -1;
}
